package com.github.yangyishe.p100;

/**
 * 最长回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/
 * The type Problem 5.
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 */
public class Problem05 {
    public static void main(String[] args) {
        String s="12323158643dddddd152123413131";

        Problem05 problem5 = new Problem05();
        String result = problem5.longestPalindrome(s);
        System.out.println(result);
    }

    /**
     * 此题关键, 是:
     * 识别回文字符串最有效率的方式, 是从最中间开始, 逐渐向外扩散的识别.
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s.length()==1) {
            return s;
        }

        char[] chars = s.toCharArray();

        int resultStartIndex=0;
        int resultEndIndex=0;
        int resultSize=0;
        int startIndex;
        int endIndex;
        // 奇数回文数计算
        for(int i=1;i<s.length()-1;i++){
            startIndex=i;
            endIndex=i;
            while(startIndex>=0&&endIndex<=s.length()-1){
                if (chars[startIndex]!=chars[endIndex]) {
                    break;
                }
                startIndex--;
                endIndex++;
            }
            if (resultSize<(--endIndex)-(++startIndex)+1) {
                resultEndIndex=endIndex;
                resultStartIndex=startIndex;
                resultSize=resultEndIndex-resultStartIndex+1;
            }
        }


        // 偶数回文数计算
        for(int i=0;i<s.length()-1;i++){
            startIndex=i;
            endIndex=i+1;
            while(startIndex>=0&&endIndex<=s.length()-1){
                if(chars[startIndex]!=chars[endIndex]){
                    break;
                }
                startIndex--;
                endIndex++;
            }
            if (resultSize<(--endIndex)-(++startIndex)+1) {
                resultEndIndex=endIndex;
                resultStartIndex=startIndex;
                resultSize=resultEndIndex-resultStartIndex+1;
            }
        }


        return s.substring(resultStartIndex,resultEndIndex+1);
    }
}
